/*
 * Team members: Fabio Canache    ID: 564693
 *               Denise Videtta   ID: 565525
 * Date:         10/06/2008
 * 
 * Project #1 - Question: 1a N-Queens
 * 
 * ALG 2008 Fall
 * Instructor: Dr. Oleg Komogortsev, TSU
 * 
 */

package nqueens;

/**
 *  This class implement the N-Queens problem  
 * 
 */
public class NQueens extends Thread {
    
    private lifequeen.LifeQueen lifeQueen;
    
    private int boardSize;
    private int diagonal;
    private int downOffSet;
    
    private int queenCol[];
    private boolean colFree[];
    private boolean upFree[];
    private boolean downFree[];
    
    private int queenCount;
    
    private int solutionsCounter;
    private int addQueenCounter;
    
    public NQueens (lifequeen.LifeQueen lifeQueen) {
        this.lifeQueen = lifeQueen;
    }
    
    @Override
    public void run () {
        this.startNQueens();
    }
        
    /**
     *  Starts the N-Queens program and runs until get all the solutions
     */
    private void startNQueens () {
        
        boardSize = this.lifeQueen.getChessBoardSize();
        diagonal = (2 * boardSize) - 1;
        downOffSet = boardSize - 1;

        queenCol = new int[boardSize];
        colFree = new boolean[boardSize];
        upFree = new boolean[diagonal];
        downFree = new boolean[diagonal];
        
        queenCount = -1;
        
        for (int i = 0; i < boardSize; i++) {
            colFree[i] = true;         
        }
        
        for (int i = 0; i < diagonal; i++) {
           upFree[i] = true;
           downFree[i] = true;
        }
        
        solutionsCounter = 0;
        addQueenCounter = 0;
        
        addQueen();
        
        lifeQueen.setNQueensDescriptionArea("Finished ...");
        lifeQueen.setCheckingRow(Integer.toString(0));
        lifeQueen.setCheckingColumn(Integer.toString(0));
        lifeQueen.setAddQueensCalls(Integer.toString(0));
        lifeQueen.enableStartNQueens(true);
        lifeQueen.enableDrawNQueensBoard(true);
        
    }
    
    /**
     *  Investigates the cells to place valid queens. Place each queen in a cell
     *  where there is not any other queen in the same row, column nor diagonal.
     *  When finish with a solution backtracks to the next option until there 
     *  are not more valid cells to investigate.
     */
    private void addQueen() {
        try {
            addQueenCounter++;
            lifeQueen.setAddQueensCalls(Integer.toString(addQueenCounter));

            queenCount++;

            for (int col = 0; col < boardSize && !lifeQueen.getStopExecution(); col++) {

                lifeQueen.setCheckingRow(Integer.toString(queenCount + 1));
                lifeQueen.setCheckingColumn(Integer.toString(col + 1));

                sleep(200);

                if (colFree[col] && upFree[queenCount + col] && downFree[queenCount - col + downOffSet]) {

                    lifeQueen.placeQueen(queenCount, col);
                    lifeQueen.setNQueensDescriptionArea("Queen placed in row " + (queenCount+1) + " and column " + (col+1) + " ...");

                    queenCol[queenCount] = col;
                    colFree[col] = false;
                    upFree[queenCount + col] = false;
                    downFree[queenCount - col + downOffSet] = false;

                    if (queenCount == (boardSize -1)) {                    

                        solutionsCounter++;
                        
                        lifeQueen.setNQueensDescriptionArea("This is the solution #" + solutionsCounter + " ...");
                        sleep(lifeQueen.getNQueensDelayTime() + 2000);
                        
                    } else {
                        
                        sleep(lifeQueen.getNQueensDelayTime());
                        
                        addQueen();
                    }

                    lifeQueen.removeQueen(queenCount, col);

                    colFree[col] = true;
                    upFree[queenCount + col] = true;
                    downFree[queenCount - col + downOffSet] = true;

                }

            }

            queenCount--;
        
       } catch (Exception e) {
            System.out.println("SLEEP ERROR!!");
        } 
    }
    
    
}
